#include "cfg.h"

/*
 this function checks if a register is already in our
 register list
*/
reg * find_reg(reg *head, simple_reg * r) {
    reg * current_reg = head;

    while(current_reg) {
        if(current_reg->r == r)
            return current_reg;
        current_reg = current_reg->next;
    }

    return NULL;
}

/*
 this function adds a new register to the list
	checks to make sure variables are not duplicated in the list
*/
void insert_reg_list(reg ** head, simple_reg * r, int * number, reg ** last_reg) {
    reg * newreg = NULL;
    
    // if i have the reg in list, i do not add it.
    if(find_reg(*head, r)) return ;

    newreg = (reg *)malloc(sizeof(reg));    
    newreg->number = ++(*number);
    newreg->r = r;
    newreg->prev = *last_reg;
    newreg->next = NULL;

    if(*head == NULL) {
        *head = newreg;        
    } else {
        (*last_reg)->next = newreg;
    }

    *last_reg = newreg;
}

/**
    - go thru each instruction
    - find the variables ( PSEDUO_REG )
    - assuming if variables are not assigned values, they are not used. 
**/
int find_variables(instr_node * instr_head, reg ** reg_list) {    
    instr_node * current_instr = instr_head;
    simple_instr * instr = NULL;
    reg * last_reg = NULL;
    int regnumber = 0;
    int insertresult = 0;

    while(current_instr) {
        instr = current_instr->instr;
        switch(simple_op_format(instr->opcode)) {
        case BASE_FORM: {
            if(instr->u.base.dst && instr->u.base.dst->kind == PSEUDO_REG) {
                insert_reg_list(reg_list, instr->u.base.dst, &regnumber, &last_reg);
            }
            if(instr->u.base.src1 && instr->u.base.src1->kind == PSEUDO_REG) {
                insert_reg_list(reg_list, instr->u.base.src1, &regnumber, &last_reg);
            }
            if(instr->u.base.src2 && instr->u.base.src2->kind == PSEUDO_REG) {
                insert_reg_list(reg_list, instr->u.base.src2, &regnumber, &last_reg);
            }
            break;
        } 
        case CALL_FORM: {
            int i;
            if(instr->u.call.proc && instr->u.call.proc->kind == PSEUDO_REG) {
                insert_reg_list(reg_list, instr->u.call.proc, &regnumber, &last_reg);
            }            
            for(i = 0; i < instr->u.call.nargs; i++)
                if(instr->u.call.args[i] && instr->u.call.args[i]->kind == PSEUDO_REG) {
                    insert_reg_list(reg_list, instr->u.call.args[i], &regnumber, &last_reg);
            }
			if(instr->u.call.dst && instr->u.call.dst->kind == PSEUDO_REG) {
				insert_reg_list(reg_list, instr->u.call.dst, &regnumber, &last_reg);
			}
            break;
        } 
        case BJ_FORM: {
            if(instr->u.bj.src && instr->u.bj.src->kind == PSEUDO_REG) {
                insert_reg_list(reg_list, instr->u.bj.src, &regnumber, &last_reg);
            }
            break;
        } 
        case LDC_FORM: {
            if(instr->u.ldc.dst && instr->u.ldc.dst->kind == PSEUDO_REG) {
                insert_reg_list(reg_list, instr->u.ldc.dst, &regnumber, &last_reg);
            }
            break;
        }
        case MBR_FORM: 
            {
                if(instr->u.mbr.src && instr->u.mbr.src->kind == PSEUDO_REG) {
                    insert_reg_list(reg_list, instr->u.mbr.src, &regnumber, &last_reg);
                }
                break;
            }
        }
        current_instr = current_instr->next;
    }
    return regnumber;
}

// this function prints the variable list by traversing the linked list
void print_variables(reg * reg_list, char * proc_name, int totalregs) {
    reg * current_reg = reg_list;

    printf("variables %s %d\n", proc_name, totalregs);
    while(current_reg) {
        printf("var %d r%d\n", current_reg->number, current_reg->r->num);
        current_reg = current_reg->next;
    }
    printf("\n");
}

// this function sets up the cfg and starts the framework
// find the use and def set for each block
// intializes lvout and lvin sets for each block
void lv_init(basic_block_node * block_head, int size, reg * reglist) {
    basic_block_node * current_block = block_head;
    basic_block_node * tail_block = NULL;
    block_ptr * stack = NULL;
    instr_node * current_instr = NULL;

    while(current_block) {
        current_block->def = new_bit_vector(size);
        set_all_bits(current_block->def, FALSE);
        current_block->use = new_bit_vector(size);
        set_all_bits(current_block->use, FALSE);
        
        current_instr = current_block->start;
        
        while(current_block->end && current_instr != current_block->end->next) {
            simple_instr * instr = current_instr->instr;
            int index;
            switch(simple_op_format(instr->opcode)) {
                case BASE_FORM: 
                    {                        
                        if(instr->u.base.src1 && instr->u.base.src1->kind == PSEUDO_REG) {
                            index = find_reg(reglist, instr->u.base.src1)->number - 1;
                            if(!get_bit(current_block->def, index))                    
                                set_bit(current_block->use, index, TRUE);
                        }
                        if(instr->u.base.src2 && instr->u.base.src2->kind == PSEUDO_REG) {
                            index = find_reg(reglist, instr->u.base.src2)->number - 1;
                            if(!get_bit(current_block->def, index))
                                set_bit(current_block->use, index, TRUE);
                        }
                        if(instr->u.base.dst && instr->u.base.dst->kind == PSEUDO_REG) {
                            reg * r = find_reg(reglist, instr->u.base.dst);
                            set_bit(current_block->def, r->number - 1, TRUE);                        
                        }
                        break;
                    }
                case CALL_FORM: 
                    {
                        int i;
                        if(instr->u.call.proc && instr->u.call.proc->kind == PSEUDO_REG) {
                            index = find_reg(reglist, instr->u.call.proc)->number - 1;
                            if(!get_bit(current_block->def, index))                    
                                set_bit(current_block->use, index, TRUE);
                        }            
                        for(i = 0; i < instr->u.call.nargs; i++)
                            if(instr->u.call.args[i] && instr->u.call.args[i]->kind == PSEUDO_REG) {
                                index = find_reg(reglist, instr->u.call.args[i])->number - 1;
                                if(!get_bit(current_block->def, index))                    
                                    set_bit(current_block->use, index, TRUE);
                            }
						if(instr->u.call.dst && instr->u.call.dst->kind == PSEUDO_REG) {
							index = find_reg(reglist, instr->u.call.dst)->number - 1;
							set_bit(current_block->def, index, TRUE);
						}
                        break;
                    }
                case BJ_FORM: {
                    if(instr->u.bj.src && instr->u.bj.src->kind == PSEUDO_REG) {
                        index = find_reg(reglist, instr->u.bj.src)->number - 1;
                            if(!get_bit(current_block->def, index))                    
                                set_bit(current_block->use, index, TRUE);
                    }
                    break;
                } 
                case LDC_FORM: {
                    if(instr->u.ldc.dst && instr->u.ldc.dst->kind == PSEUDO_REG) {
                        index = find_reg(reglist, instr->u.ldc.dst)->number - 1;
                        set_bit(current_block->def, index, TRUE);
                    }
                    break;
                }
                case MBR_FORM: 
                    {
                        if(instr->u.mbr.src && instr->u.mbr.src->kind == PSEUDO_REG) {
                            index = find_reg(reglist, instr->u.mbr.src)->number - 1;
                            if(!get_bit(current_block->def, index))                    
                                set_bit(current_block->use, index, TRUE);
                        }
                        break;
                    }
            }
            current_instr = current_instr->next;
        }

        current_block->lvin = new_bit_vector(size);
        current_block->lvout = new_bit_vector(size);

        // intializing LVin(b) to USE(b)
        copy_bits(current_block->lvin, current_block->use);
        
        tail_block = current_block;
        current_block = current_block->next;
    }

    // intializing the Exit node to be NULL
    set_all_bits(tail_block->lvin, FALSE);

	// we keep doing depth first traversal until the framework informs no changes
    while(dfa_start(tail_block, lv_meet, lv_transferfunc, &stack, 1)) {
        stack = NULL;           
    };    
}


// prints the def set
void print_def_set(basic_block_node * block_head, char * proc_name, int totalblocks) {
    basic_block_node * current_block = block_head;
    int i;

    printf("def_lv_sets %s %d\n", proc_name, totalblocks);
    
    while(current_block) {
        printf("def_lv %d ", current_block->number);
        for(i = 0; i < current_block->def->num_bits; i++)
            printf("%d", get_bit(current_block->def, i) ? 1 : 0);
        current_block = current_block->next;
        printf("\n");
    }
    printf("\n");
}

// prints the use set
void print_use_set(basic_block_node * block_head, char * proc_name, int totalblocks) {
    basic_block_node * current_block = block_head;
    int i;

    printf("use_lv_sets %s %d\n", proc_name, totalblocks);
    while(current_block) {
        printf("use_lv %d ", current_block->number);
        for(i = 0; i < current_block->use->num_bits; i++)
            printf("%d", get_bit(current_block->use, i) ? 1 : 0);
        current_block = current_block->next;
        printf("\n");
    }
    printf("\n");
}

// prints lvout set
void print_lvout(basic_block_node * block_head, char * proc_name, int totalblocks) {
basic_block_node * current_block = block_head;
    int i;

    printf("live_variables %s %d\n", proc_name, totalblocks);
    while(current_block) {
        printf("live_out %d ", current_block->number);
        for(i = 0; i < current_block->lvout->num_bits; i++)
            printf("%d", get_bit(current_block->lvout, i) ? 1 : 0);
        current_block = current_block->next;
        printf("\n");
    }
    printf("\n");
}

// find if a block is already in the stack
// this is used to keep track if a node is already visited.
block_ptr * find_in_stack(block_ptr * stack, basic_block_node * block) {
    block_ptr * current = stack;

    while(current) {
        if(current->block == block)
            return current;
        current = current->next;
    }

    return NULL;
}

// prints the stack ( used for debugging )
void print_stack(block_ptr * stack) {
    block_ptr * current = stack;
    printf("stack > ");
    while(current) {
        printf("%d ", current->block->number);
        current = current->next;
    }

    printf("\n");
}

// the framework function
// this function requires that the cfg is properly intialized
int dfa_start(basic_block_node * block, MeetOpFunc meet_op, TransferFunc transfer_func, block_ptr ** stack, int dir) {    
    block_ptr * predecessor = block->predecessor;    
	block_ptr * successor = block->successor;
    int result = 0;    
    
    if(find_in_stack(*stack, block)) {
        return FALSE;        
    }

    insert_on_stack(stack, block);

    result = meet_op( block );
    result = result || transfer_func ( block );
    
	if(dir)
	{
    	while(predecessor) {
        	result = result || dfa_start(predecessor->block, meet_op, transfer_func, stack, dir);
        	predecessor = predecessor->next;
    	}
	}
	else {
		while(successor) {
			result = result || dfa_start(successor->block, meet_op, transfer_func, stack, dir);
			successor = successor->next;
		}
	}
    
    return result;
}

// transferfunc for live variables
int lv_transferfunc( basic_block_node * block) {
    bit_vector * oldin = new_bit_vector(block->lvin->num_bits);     
    bit_vector * result = new_bit_vector(block->lvin->num_bits);    

    copy_bits(oldin, block->lvin);                                  // oldin = LVin(b)
    set_all_bits(result, FALSE);

    copy_bits(result, block->lvout);
    subtract_bits(result, block->def);                              // LVout(b) - Def(b)
    or_bits(result, block->use);                                    // Use(b) U result(b)

    copy_bits(block->lvin, result);

    //*lvin = block->lvin;

    return !bits_are_equal(oldin, block->lvin);
}

// meet operator for live variables
int lv_meet( basic_block_node * block) {
    block_ptr * successor = block->successor;
    bit_vector * union_set = new_bit_vector(block->lvout->num_bits);

    set_all_bits(union_set, FALSE);

    while(successor) {
        or_bits(union_set, successor->block->lvin);
        successor = successor->next;
    }

    copy_bits(block->lvout, union_set);

    //*lvout = block->lvout;

	return FALSE;
}
